1. Field of Invention
This invention relates to the automatic generation of programs where the automated generation systems are faced with the problem of creating and refining separated but constraint related parts of the program, where the separation of the parts may occur in both the time and space domain or just one of the two, where those parts are related by one or more non-local constraints (i.e., constraints that include all of the separated parts but perforce must span the separation gaps) such that those non-local constraints require that generator-based refinements or alterations of one of the constrained parts will determine and effect compensating generator-based refinements or alterations to the related parts so as to preserve the invariant properties of the overall constraint relationship and thereby preserve a consistent set of interdependencies among the parts, where such automatic generation systems provide various kinds of facilities for refining execution platform neutral specifications of computations into computer programs expressed in conventional programming languages such as, C, C++, Java and similar languages often referred to by the term General Programming Languages (or GPLs), and where such automatically generated computer programs are frequently required to exploit high capability facilities of such execution platforms including but not limited to fine grain, middle grain and large grain parallelism facilities, distributed facilities, security facilities, mobile facilities, remote services facilities, associated processing services facilities, situational facilities (e.g., awareness, position, movement, response, and so forth), quantum computing facilities and other or future high capability facilities.
2. Description of Prior Art
Adds Machinery Consistent with Previous Patent Application
This patent application enhances, supplements and extends the machinery of patent application Ser. No. 12/363,738 by introducing a new mechanism to couple separated elements of the target program being created by some domain specific generator (e.g., DSLGen, the reduction to practice generator of patent application Ser. No. 12/363,738) as well as to couple separated generative transformations that must coordinate their activities across separated generation times and separated target program locales.
Constraint Satisfaction Programming
Constraint satisfaction programming (or CSP) research is a sound-alike topic but it is NOT focused on using constraints to guide the construction and parallelization (or other program reorganization techniques) of general computer programs in the sense considered in this invention. And more specifically, it is not focused on dealing with explicitly coupled constraints on specific objects (i.e., program parts) and explicitly coupled transformations on specific, separated program parts where the constraints, their separated data and the related transformations inhabit a special, common context. In that special, common context, the state of one data item or transformation is inexorably dependent on the state of the others such that the change of any one requires compensating changes to the others.
For more and deeper background on CSP, see the following references:    Barták, R.: “Constraint Programming: In Pursuit of the Holy Grail,” in Proceedings of the Week of Doctoral Students (WDS99), Part IV, MatFyzPress, Prague (June 1999)555-564;    Borning, A.: “The Programming Language Aspects of ThingLab, A Constraint-Oriented Simulation Laboratory,” in ACM Transactions on Programming Languages and Systems, 3(4) (1981) 252-387;    Apt, Krzysztof: Principles of Constraint Programming, Cambridge University Press, Cambridge, UK (2003); and    Schulte, Christian and Stuckey, Peter J.: Efficient Constraint Propagation Engines, ACM Transactions on Programming Languages and Systems, Vol. 31, No. 1, (2009).
CSP, on the other hand, is the process of finding a solution (i.e., a vector of values) for a set of variables that satisfy a set of constraints. It is typically focused on and characterized by computational models that use largely global constraints (dynamically) to guide the execution of a program searching a very large search space for potential solutions to a problem (e.g., finding DNA sub-segments that may be part of a single longer segment based on common sub-segments patterns). Any specific relationship among specific items of data or specific transformations on that data in CSP is purely an indirect consequence of the overall algorithm and global problem constraints. There is no machinery for direct, explicit constraint-based connections or couplings between specific data items, constraints on those specific data items or specific transformations on those specific data items. The idea of CSP is that the constraints can (possibly) reduce the search of an infeasibly large search space to a feasible size by determining that large portions of that space do not contain or are unlikely to contain the solution based on some macro-properties (i.e., global properties) of that large subspace. CSP is mostly focused on constraint satisfaction problems that are best characterized as a “mathematically oriented process akin to solving equations” where the “equations” are the constraints. The problems are mostly combinatorial in nature and the approaches are mostly methods of searching some large solution space for an answer meeting the set of constraints. The constraints are often propagated over the data description as a mechanism of guiding the execution of the search. Typical example problems are:                Simulations of real-world systems,        Finding DNA sequences given a large number of overlapping sub-sequences,        Determining protein structures,        Graphic layout solutions (e.g., projecting a complex network onto a two dimensional surface in a way that makes it easy to understand),        Configuring or designing networks such that they meet some set of constraints,        Scheduling problems (i.e., scheduling events given a set of restrictions), and        Planning problems (akin to scheduling problems).        
In contrast to this invention, compensating effects are not directly triggered by remote refinement actions in CSP. In CSP, the problem representation generally comprises two distinct languages, the language that expresses the constraints and the language that defines the data. In the CSP world, the constraint aspect of the problem is formulated as mathematical forms (e.g., logical or equational forms) and that is the conventional way in which most constraint truths are expressed. The form or structure of the data does not imply aspects of the underlying constraint truths. Certainly, the data may have inherent properties that are used but this does not provide that same kind of explicit, operational coupling and connection among individual data items and individual transformations that is manifest in this invention.
In summary, the broad structure of and approach to CSP problems is quite different from that of automatic program generation problems in general and from the constraint-based automatic program generation method using this invention in particular.
Previous Work by This Author
Other automatic program generation solutions also are quite different in structure and mechanism. In previous work by this author (Ted J. Biggerstaff, “A New Architecture for Transformation-Based Generators,” IEEE Transactions on Software Engineering, Vol. 20, No. 12, December 2004), transformations were related to data items through property structures associated with said data items, however, the transformations in said work were triggered by simple state information and they did not manifest a bidirectional, operational coupling that would effect the compensating changes necessitated by remote coupling as defined in this invention.
Aspect Oriented Programming
Aspect Oriented Programming (AOP) is another superficially similar but fundamentally different generation technique. (See Tzilla Elrad, Robert E. Filman, Atef Bader, (Eds.), “Special Issue on Aspect-Oriented Programming,” Communications of the ACM, vol. 44, no. 10, pp. 28-97, 2001.) AOP seeks to separately specify aspects of the target program in a GPL level language and then as a separate process, weave those separate aspects into a design that is more computationally optimal (but a design that is by necessity less modular). For example, one might specify the essence of a computation separately from a cache-based optimization for that computation. AOP is an optimization oriented approach that does not use the mechanisms of this invention to deal with non-localized constraints and to the best of the authors knowledge, AOP does not deal with non-localized constraints at all. Even if by some stretch of logic, AOP might be said to implicitly handle non-localized constraints, it is certainly not via the machinery used in this invention.
Another difference is that AOP is working largely in the GPL domain and not the problem domain or even in the programming process domain (i.e., the domain that specifies the process of formulating abstract design entities and step by step refining them into concrete program entities). That is to say, the domain abstractions that this invention deals with are not a part of an AOP specification as explicit entities. For example, an implementation free specification of a computation is perforce not in the GPL domain by the very virtue of the fact that it is an implementation independent specification of a computation.
Further, the domain specific entities and relationships used in this invention (e.g., an abstract design pattern) would be difficult to express in an AOP specification because of the AOP bias toward concrete, GPL representations, which impedes the objective of this invention to create provisional, partial design edifices and defer making concrete GPL-level decisions until the broad architectural frameworks have been derived.
Additionally, the process of leveraging domain knowledge to formulate provisional but still incomplete designs in order to decompose the generation process into a series of steps that solve smaller, simpler problems in the course of achieving an overall generation goal, falls outside of the context of AOP. In the context of this invention, determining that instruction level parallelism is possible and desirable is easily made at an early stage of the processing when the computation specification is in a highly domain specific (and abstract) form and when those domain specific forms can suggest the possibility of instruction level parallelism and some of the abstract design details of it. However, the low level details needed to formulate the actual parallel instructions (e.g., an existing and populated coefficient array) have not been developed at this early stage. Later, when those needed low level details do become available, the early preparation work informs the later stages about some of the objectives, entities and constraints that will have to be incorporated into the process that derives the actual low level parallel instructions.
Another key difference is that AOP has no machinery for non-localized constraints connecting and mediating the changes to program entities and to programming process entities separated across the physical program, nor any concept of those same entities connected across generation times (e.g., connecting entities in a design stage with entities in a GPL stage).